package arrAndstr;

/*
    合并两个有序数组
    双指针 --> 实现O(n+m)， 但费空间
    插入排序，原地
 */

public class T88 {

    public static void main(String[] args) {
        int[] array1 = new int[]{1,2,3,0,0,0};
        int[] array2 = new int[]{2,5,6};

        merge(array1, array1.length, array2, array2.length);
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] newArray = new int[m+n];

        int left1 = 0, left2 = 0, index = 0;
        while(left1 < m || left2 < n) {
            if(left1 >= m) {
                copyElement(newArray, index, nums2, left2);
                break;
            }
            if(left2 >= n) {
                copyElement(newArray, index, nums1, left1);
                break;
            }
            if(nums1[left1] <= nums2[left2]) {
                newArray[index++] = nums1[left1++];
            } else {
                newArray[index++] = nums2[left2++];
            }
        }
        copyElement(nums1, 0, newArray, 0);
    }

    public static void swap(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    public static void copyElement(int[] newArray, int newIndex, int[] oldArray, int oldIndex){
        while(newIndex<newArray.length) {
            newArray[newIndex++] = oldArray[oldIndex++];
        }
    }
}
